import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Test {
    public int maxArea(int[] height) {
        int left = 0;
        int right = height.length-1;
        int maxV = Math.min(height[left],height[right]) * (right - left);

        while(left < right) {
            if(height[left] < height[right]) {
                left++;
            } else {
                right--;
            }
            int newV = Math.min(height[left],height[right]) * (right - left);
            if(maxV < newV) {
                maxV = newV;
            }
        }

        return maxV;
    }

    public int triangleNumber(int[] nums) {
        //排序
        Arrays.sort(nums);

        //双指针算法
        int count = 0;
        for(int target = nums.length - 1; target >= 2; target--) {
            int left = 0;
            int right = target - 1;
            while(left < right) {
                if(nums[left] + nums[right] > nums[target]) {
                    count += right - left;
                    right--;
                } else {
                    left++;
                }
            }
        }

        return count;
    }

    public int[] twoSum(int[] price, int target) {
        int left = 0;
        int right = price.length - 1;
        int[] ret = new int[2];
        while(left < right) {
            if(price[left] + price[right] == target) {
                break;
            } else if(price[left] + price[right] > target) {
                right--;
            } else {
                left++;
            }
        }
        ret[0] = price[left];
        ret[1] = price[right];
        return ret;
    }

    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> list = new ArrayList<>();
        Arrays.sort(nums);
        for(int k = nums.length - 1; k >= 2;) {
            int i = 0;
            int j = k - 1;
            while(i < j) {
                if(nums[i] + nums[j] + nums[k] == 0) {
                    List<Integer> l = new ArrayList<>();
                    l.add(nums[i]);
                    l.add(nums[j]);
                    l.add(nums[k]);
                    list.add(l);
                    i++;
                    j--;
                    while(i < j && nums[i-1] == nums[i]) {
                        i++;
                    }
                    while(j > i && nums[j+1] == nums[j]) {
                        j--;
                    }
                } else if(nums[i] + nums[j] + nums[k] < 0) {
                    i++;
                } else {
                    j--;
                }
            }
            k--;
            while(k >= 2 && nums[k+1] == nums[k]) {
                k--;
            }
        }

        return list;
    }
    public static List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> list = new ArrayList<>();
        Arrays.sort(nums);
        boolean fc = false;
        int c = 0;
        for(int d = nums.length - 1; d >= 3;) {
            if(!fc) {
                c = d-1;
                fc = true;
            }
            int a = c - 2;
            int b = c - 1;
            int flag = target - nums[d] - nums[c];
            while(a < b) {
                if(nums[a] + nums[b] == flag) {
                    list.add(new ArrayList<Integer>(Arrays.asList(nums[a],nums[b],nums[c],nums[d])));
                    a++;
                    b--;
                    while(a < b && nums[a-1] == nums[a]) {
                        a++;
                    }
                    while(a < b && nums[b+1] == nums[b]) {
                        b--;
                    }
                } else if(nums[a] + nums[b] < flag) {
                    a++;
                } else {
                    b--;
                }
            }
            d--;
            while(d >= 3 && nums[d+1] == nums[d]) {
                d--;
            }
            c = d-1;
            while(c >= 2 && nums[c+1] == nums[c]) {
                c--;
            }
        }

        return list;
    }

    public static List<List<Integer>> fourSum4(int[] nums, int target) {
        List<List<Integer>> list = new ArrayList<>();
        if(nums == null || nums.length < 4) {
            return list;
        }
        Arrays.sort(nums);
        for(int a = 0; a < nums.length - 3;) {
            for(int b = a+1; b < nums.length - 2;) {
                int c = b+1;
                int d = nums.length - 1;
                long flag = target - (long)nums[a] - (long)nums[b];
                while(c < d) {
                    if((long)nums[c] + (long)nums[d] == flag) {
                        list.add(new ArrayList<Integer>(Arrays.asList(nums[a],nums[b],nums[c],nums[d])));
                        c++;
                        d--;
                        while(c < d && (long)nums[c-1] == (long)nums[c]) {
                            c++;
                        }
                        while(c < d && (long)nums[d+1] == (long)nums[d]) {
                            d--;
                        }
                    } else if((long)nums[c] + (long)nums[d] < flag) {
                        c++;
                    } else {
                        d--;
                    }
                }
                b++;
                while(b < nums.length - 2 && (long)nums[b-1] == (long)nums[b]) {
                    b++;
                }
            }
            a++;
            while(a < nums.length - 3 && (long)nums[a-1] == (long)nums[a]) {
                a++;
            }
        }
        return list;
    }

    public static void main(String[] args) {
        int[] nums = {-2,-1,-1,1,1,2,2};
        int target = 0;
        //fourSum4(nums,target);
    }
}
